package example7;

//647. 回文子串
public class LeetCode647 {
    public static void main(String[] args) {

    }
}

/**
 * 方法一：找出所有的回文中心，然后分别再用两个索引分别从回文中心向两边扩展，如果两边相等，那么这两边之间的子串
 * 就是回文子串，总数sum++，如果不等，那么就不是，而且以当前中心为回文中心的所有回文子串都已找完，遍历下一个回文中心。
 * 时间复杂度 O(n2)      空间复杂度 O(1)
 * 方法二：还可以枚举出所有的子串，然后依次遍历这些子串是否是回文子串 时间 O(n3)   空间 O(1)
 *
 * 下面这种方法是方法一的回文中心扩展的
 */
class Solution647 {
    public int countSubstrings(String s) {
        if(s == null || s.equals(""))   return 0;
        int sum = 0;
        //先找所有奇数长度的回文子串
        for(int i=0;i<s.length();i++){
            for(int x=i,y=i;x>=0&&y<s.length();x--,y++){
                if (s.charAt(x) == s.charAt(y)){
                    sum++;
                }else{
                    break;
                }
            }
        }
        //再找所有偶数长度的回文子串
        for(int i=0;i<s.length()-1;i++){
            for(int x=i,y=i+1;x>=0&&y<s.length();x--,y++){
                if (s.charAt(x) == s.charAt(y)){
                    sum++;
                }else{
                    break;
                }
            }
        }
        return sum;
    }
}
